package minimumJumps;

import java.util.*;

public class Solution {
    boolean[] forbiddenBol;
    boolean[][] visited; // vis[i][0] 表示通过向左的方式来过这 vis[i][1]表示通过向右的方式来过这
    int ans = Integer.MAX_VALUE;
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        int t = Arrays.stream(forbidden).max().getAsInt();
        int lower = 0, upper = Math.max(Arrays.stream(forbidden).max().getAsInt() + a, x) + b;
        visited = new boolean[upper+1][2];
        forbiddenBol = new boolean[Math.max(upper,t)+1];
        for (int f: forbidden) {
            forbiddenBol[f] = true;
        }
        bfs(0,0,x,a,b,upper,0);
        return ans == Integer.MAX_VALUE?-1:ans;
    }
    private void bfs(int time,int cur,int target,int a,int b,int up,int lastJumpType) {
        if(cur == target) {
            System.out.println("找到了一条路径");
            ans = Math.min(ans,time);
        }
        if(cur > up) {
            return;
        }
        if(cur<0) {
            return;
        }
        if(forbiddenBol[cur] == true) {
            return ;
        }
        if(visited[cur][lastJumpType] == true) {
            return;
        }
        visited[cur][lastJumpType] = true;
        if(lastJumpType == 0) {
            bfs(time+1,cur+a,target,a,b,up,1);
        }else {
            bfs(time+1,cur+a,target,a,b,up,1);
            bfs(time+1,cur-b,target,a,b,up,0);
        }
    }
}
